package start;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map.Entry;

import plan.DistanceMatrix;
import plan.Plan;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] cities = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R"};   
		DistanceMatrix d = DistanceMatrix.createDM();
		
		ArrayList<Plan> generation = new ArrayList<Plan>();
		
		for(String city : cities){
			Plan p = createShortestFrom(city, d);
			
			System.out.println(p+" - "+p.getDistance());
			generation.add(p);
			
			p = createLongestFrom(city, d);
			p.mutate(3);
			System.out.println(p+" - "+p.getDistance());
			generation.add(p);
		}
		
		System.out.println("");
		int it = 1, maxIt = 5000;
		while(it < maxIt){
			System.out.println("Iteration: "+it);
			
			Collections.sort(generation);
			
			int rnd = (int) (Math.random()*generation.size());
			Plan rndPlan = generation.get(rnd);
			generation = getFittest(generation, 25);
			generation.add(rndPlan);
			
			
			for(Plan p : generation){
				System.out.println(p+" - "+p.getDistance());
			}
			
			ArrayList<Plan> newGen = new ArrayList<Plan>();
			for(Plan p1 : generation){
				for(Plan p2 : generation){
					if(p1 != p2){
						Plan p = Plan.createChild(p1, p2);
						p.mutate(1);
						while(newGen.contains(p)){
							p.mutate(1);
						}
						newGen.add(p);
					}
				}
			}
			
			for(Plan p : getFittest(generation, 5)){
				if(!newGen.contains(p))
					newGen.add(p);
			}
			generation = newGen;
			it++;
		}
		System.out.println("Fittest:");
		for(Plan p : getFittest(generation, 8)){
			System.out.println(p+" - "+p.getDistance());
		}
	}
	
	private static Plan createShortestFrom(String s, DistanceMatrix d){
		String route = s;
		String current = s;
		while(route.length() < d.getDistancesFromCity(s).size()+1){
	        int min = Integer.MAX_VALUE;
	        String next = "";
			for(Entry<String, Integer> e : d.getDistancesFromCity(current).entrySet()){
				if(e.getValue() < min && route.indexOf(e.getKey()) == -1){
					min = e.getValue();
					next = e.getKey();
				}
			}
			route += next;
			current = next;
		}
		return new Plan(route, d);
	}
	
	private static Plan createLongestFrom(String s, DistanceMatrix d){
		String route = s;
		String current = s;
		while(route.length() < d.getDistancesFromCity(s).size()+1){
	        int max = Integer.MIN_VALUE;
	        String next = "";
			for(Entry<String, Integer> e : d.getDistancesFromCity(current).entrySet()){
				if(e.getValue() > max && route.indexOf(e.getKey()) == -1){
					max = e.getValue();
					next = e.getKey();
				}
			}
			route += next;
			current = next;
		}
		return new Plan(route, d);
	}
	
	private static ArrayList<Plan> getFittest(ArrayList<Plan> list, int n){
		Collections.sort(list);
		List<Plan> l = list.subList(0, Math.min(list.size(), n));
		
		ArrayList<Plan> result = new ArrayList<Plan>();
		result.addAll(l);
		return result;
	}
}
